package Easy.String;

//给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
//
// 示例 1：
//
//输入:a = "11", b = "1"
//输出："100"
//
// 示例 2：
//
//输入：a = "1010", b = "1011"
//输出："10101"
//
// 提示：
// 1 <= a.length, b.length <= 10⁴
// a 和 b 仅由字符 '0' 或 '1' 组成
// 字符串如果不是 "0" ，就不含前导零


//leetcode submit region begin(Prohibit modification and deletion)
public class AddBinary {
    public String addBinary(String a, String b) {
        StringBuilder ans = new StringBuilder();
        // carry表示进位
        int carry = 0;
        int i = a.length() - 1, j = b.length() - 1;
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (i >= 0) {
                // 将字符转换为数字
                sum += a.charAt(i--) - '0';
            }
            if (j >= 0) {
                sum += b.charAt(j--) - '0';
            }
            // 取余表示当前位的值
            ans.append(sum % 2);
            // 取整表示进位
            carry = sum / 2;
        }
        // 如果最后还有进位，加上
        if (carry > 0) {
            ans.append(carry);
        }
        // 由于是从低位开始加的，所以需要翻转
        return ans.reverse().toString();
    }
}
//leetcode submit region end(Prohibit modification and deletion)

